// Copyright (c) [Year] [name of copyright holder]
// [Software Name] is licensed under Mulan PSL v2.
// You can use this software according to the terms and conditions of the Mulan PSL v2. 
// You may obtain a copy of Mulan PSL v2 at:
//          http://license.coscl.org.cn/MulanPSL2 
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.  
// See the Mulan PSL v2 for more details.

/*!
 * \autor captainpeng
 * \date 2018-9-5
 * \update 2019-1-15
 * \version 1.0
 * \copyright
 */

#ifndef MY_SEQ_HPP
#define MY_SEQ_HPP

#include<queue>
#include"mystd.hpp"
#include"function.hpp"
#include"buffer.hpp"

namespace my{

    template<typename ElementType>
    class seqT{
    private:
        using bufType = buffer<ElementType>;

    public:
        using elementType = typename bufType::elementType;
        using elementPtr = typename bufType::elementPtr;
        using elementRef = typename bufType::elementRef;
        using elementConstRef = typename bufType::elementConstRef;
        using elementConstPtr = typename bufType::elementConstPtr;
	
        using iteratorType = typename bufType::iteratorType;
        using iteratorConstType = typename bufType::iteratorConstType;

        bufType mBuf;
        size_t mSize;

    private:
        elementRef get(const long pos){
            long size = (size_t)mSize;
            if(pos >= size){
                // 1. 设置要 resize 的长度 rsize ，当容量还能满足的时候 rsize 为 0
                size_t rsize = (size_t)((pos < mBuf.size())? 0:pos/8*8+0x10);
                // std::cout<<"size="<<size<<", i/8*8+0x10="<<i/8*8+0x10<<",mBuf.size()="<<mBuf.size()
                // 	 <<",i/8="<<i/8<<std::endl;
                // 2. 当 rsize == 0 的时候，该函数什么都不做
                mBuf.resize(rsize);

                // 3. 初始化扩展的部份
                // for(long i = (long)mSize; i <= pos; ++i)
                //     mBuf[i] = *nil<elementType>();

                // 4. 重置 mCurEnd 指针的位置
                mSize = (size_t)(pos+1);
            }

            return bufType::index(pos, mBuf.begin(), mSize);
        }

    public:
        static int comp(const seqT & lhs, const seqT & rhs){
            iteratorConstType it1 = lhs.begin();
            iteratorConstType end1 = lhs.end();
            iteratorConstType it2 = rhs.begin();
            iteratorConstType end2 = rhs.end();
            int result = 0;
            for(;it1 != end1 && it2 != end2; ++it1, ++it2){
                result = func<elementType>::comp((*it1), (*it2));
                if(result != 0)
                    break;
            }

            if(result == 0){
                result = func<size_t>::comp(lhs.size(), rhs.size());
            }

            return result;
        }

    public:
        seqT(): mBuf(), mSize(0){}

        seqT(size_t size): mBuf(size), mSize(0){}

        seqT(const seqT & s):mBuf(s.mBuf), mSize(s.mSize){}

        seqT(seqT && s):mBuf(std::move(s.mBuf)), mSize(s.mSize){
            s.mSize = 0;
        }

        seqT(const bufType & buf):mBuf(buf), mSize(mBuf.mSize){}
        seqT(bufType && buf):mBuf(std::move(buf)), mSize(mBuf.mSize){}

        seqT(const bufType & buf, size_t size): mBuf(buf){
            if(size > (size_t)buf.size())
                mSize = (size_t)buf.size();
            else
                mSize = size;
        }

        seqT(const bufType && buf, size_t size): mBuf(std::move(buf)){
            if(size > (size_t)buf.size())
                mSize = (size_t)buf.size();
            else
                mSize = size;
        }

        seqT(const std::initializer_list<elementType> & list):mBuf(list), mSize((size_t)mBuf.size()){}

        seqT & operator=(const seqT & s){
			mBuf.copy(s.mBuf);
            mSize = s.mSize;
            return *this;
        }

        seqT & operator=(seqT && s){
            mBuf = std::move(s.mBuf);
            mSize = s.mSize;
            s.mSize = 0;
            return *this;
        }

        seqT & operator=(const std::initializer_list<elementType> & list){
            if(mBuf.size() >= list.size()){
                // for(auto it = list.begin(), eit = list.end(), i = 0; it != eit; ++it, ++i){
                //     mBuf[i] = std::move(*it);
                // }
                std::copy(list.begin(), list.end(), mBuf.begin());
            }else
                mBuf = list;
            mSize = list.size();
            return *this;
        }
	
        inline long size() const {
            return (long)mSize;
        }

        inline long ssize() const {
            return -((long)mSize);
        }

        inline size_t capacity() const {
            return mBuf.size();
        }

        inline iteratorConstType begin() const {
            return mBuf.begin();
        }

        inline iteratorConstType end() const {
            return mBuf.begin() + mSize;
        }

        inline iteratorType begin(){
            return mBuf.begin();
        }

        inline iteratorType end(){
            return mBuf.begin() + mSize;
        }

        elementRef back(){
            return bufType::index(-1, mBuf.begin(), mSize);
        }
        
        void resize(size_t size){
            size_t capacity = (size < (size_t)mBuf.size())? 0:size/8*8+0x10;
            mBuf.resize(capacity);
            mSize = size;
        }

        // 改变 seq 的长度
        // 如果 count 为负数，则把长度减下来
        // 如果 count 为正数，则把长度加上去
        void chsize(const int count){
            resize(mSize + count);
        }

        void clear(){
            mSize = 0;
        }

        inline elementRef operator[](const int pos){
            return get(pos);
        }

        inline elementConstRef operator[](const int pos) const {
            seqT & tmp = const_cast<seqT & >(*this);
            return bufType::index(pos, tmp.mBuf.begin(), tmp.mSize);
        }

        inline elementRef operator*(){
            return *mBuf;
        }

        template<typename CALL, typename ... ARGS>
        void each(const CALL & call, ARGS && ... args){
            for(auto it = begin(); it != end(); ++it)
                if(!call((*it), std::forward<ARGS>(args)...))
                    return ;
        }
    };
    
    // 这是一段关于 seqT 运算的函数 包括
    // 组合 operator+ ， 把两个 seqT 组合成一个 seqT
    // 组合赋值 operator+= , 把右边的 seqT 添加至左边里
    // 去除 operator- , 把左边 seqT 中存在于右边的 seqT 的元素去除掉
    // 去除赋值 operator-=  ,同上,不过会修改左边的 seqT
    // 向后加入 operator<<
    // 向后删除 operator>>

    template<typename ElementType>
    seqT<ElementType> & operator<<(seqT<ElementType> & lhs,
                                  const typename seqT<ElementType>::elementType & rhs){

        lhs.chsize(1);
        lhs.back() = rhs;
        return lhs;
    }

    template<typename ElementType>
    seqT<ElementType> & operator>>(seqT<ElementType> & lhs,
                                  typename seqT<ElementType>::elementType & rhs){
        if(lhs.size() != 0){
            rhs = std::move(lhs.back());
            lhs.chsize(-1);
        }
        return lhs;
    }
    
    template<typename ElementType>
    seqT<ElementType> operator+(const seqT<ElementType> & lhs,const seqT<ElementType> & rhs){
        int len = lhs.size()+rhs.size();
        buffer<ElementType> buf(len);
        for(int i = 0; i < len; ++i){
            buf[i] = (i < lhs.size())? lhs[i]:rhs[i-lhs.size()];
        }

        return seqT<ElementType>(std::move(buf));
    }

    template<typename ElementType>
    seqT<ElementType> operator+(const seqT<ElementType> & lhs,
                               const typename seqT<ElementType>::elementType & rhs){
        int len = lhs.size()+1;
        buffer<ElementType> buf(len);
        for(int i = 0; i < lhs.size(); ++i){
            buf[i] = lhs[i];
        }
        buf[lhs.size()]=rhs;

        return seqT<ElementType>(std::move(buf));
    }

    template<typename ElementType>
    seqT<ElementType> operator-(const seqT<ElementType> & lhs,const seqT<ElementType> & rhs){
        int len = lhs.size();
        int cur = 0;
        buffer<ElementType> buf(len);
        for(int i=0;i < len; ++i){
            if(std::find(rhs.begin(),rhs.end(),lhs[i]) == rhs.end())
                buf[cur++]=lhs[i];
        }

        return seqT<ElementType>(std::move(buf),cur);
    }

    template<typename ElementType>
    seqT<ElementType> operator-(const seqT<ElementType> & lhs,
                               const typename seqT<ElementType>::elementType & rhs){
        int len = lhs.size();
        int cur = 0;
        buffer<ElementType> buf(len);
        for(int i=0;i < lhs.size();++i){
            if(lhs[i] != rhs)
                buf[cur++]=lhs[i];
        }
	
        return seqT<ElementType>(std::move(buf),cur);
    }

    template<typename ElementType>
    seqT<ElementType> & operator+=(seqT<ElementType> & lhs,const seqT<ElementType> & rhs){
        for(int i = 0; i < rhs.size(); ++i)
            lhs[lhs.size()] = rhs[i];
        return lhs;
    }

    template<typename ElementType>
    seqT<ElementType> & operator+=(seqT<ElementType> & lhs,
                                  const typename seqT<ElementType>::elementType & rhs){
        lhs[lhs.size()] = rhs;
        return lhs;
    }

    template<typename ElementType>
    seqT<ElementType> & operator-=(seqT<ElementType> & lhs,const seqT<ElementType> & rhs){
        // 一个可以把存在于 rhs 的元素后挪到 lhs 的最后面
        // 1.队列 q 用来纪录最新的存在于 rhs 元素的位置
        std::queue<int> q;

        // 2.遍历 lhs 所有元素
        for(int i=0;i < lhs.size();++i){
            // 3.若存在于 rhs 则把该位置入队列 q
            if(std::find(rhs.begin(),rhs.end(),lhs[i]) != rhs.end()){
                q.push(i);
                // 4.若不存在且队列 q 不为空，交换队列第一个位置和当前位置的元素
            }else if(!q.empty()){
                std::swap(lhs[q.front()],lhs[i]);
                q.pop();
                q.push(i);
            }
        }
        // 5.若最后队列也不为空，则更改 lhs 的 size
        if(!q.empty()) lhs.resize(q.front());
        return lhs;
    }

    template<typename ElementType>
    seqT<ElementType> & operator-=(seqT<ElementType> & lhs,
                                  const typename seqT<ElementType>::elementType & rhs){
        //同上
        std::queue<int> q;
	
        for(int i=0;i < lhs.size();++i){
            if(lhs[i] == rhs){
                q.push(i);
            }else if(!q.empty()){
                std::swap(lhs[q.front()],lhs[i]);
                q.pop();
                q.push(i);
            }
        }

        if(!q.empty()) lhs.resize(q.front());
        return lhs;
    }

    // 比较运算符重载
    template<typename ElementType>
    bool operator==(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return (lhs.size() == rhs.size()) && seqT<ElementType>::comp(lhs, rhs) == 0;
    }

    template<typename ElementType>
    bool operator!=(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return !(lhs == rhs);
    }

    template<typename ElementType>
    bool operator>(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return seqT<ElementType>::comp(lhs, rhs) > 0;
    }

    template<typename ElementType>
    bool operator>=(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return seqT<ElementType>::comp(lhs, rhs) >= 0;
    }

    template<typename ElementType>
    bool operator<(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return seqT<ElementType>::comp(lhs, rhs) < 0;
    }

    template<typename ElementType>
    bool operator<=(const seqT<ElementType> & lhs, const seqT<ElementType> & rhs){
        return seqT<ElementType>::comp(lhs, rhs) <= 0;
    }

    template<typename ElementType>
    std::ostream & operator<<(std::ostream & os, const seqT<ElementType> & rhs){
        os<<'{';
        for(auto it=rhs.begin();it != rhs.end();++it){
            if(it == rhs.end()-1)
                os<<(*it);
            else
                os<<(*it)<<',';
        }
        return os<<'}';
    }

    template<typename T>
    using seq = seqT<my::info_type_t<T>>;

}
#endif
